#include <stack>
#include <bits/stdc++.h>
#include <functional>
using namespace std;

/*
LCR 055. 二叉搜索树迭代器
已解答
中等
相关标签
相关企业
实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

输入：
inputs = ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
inputs = [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出：
[null, 3, 7, true, 9, true, 15, true, 20, false]

解释：
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // 返回 3
bSTIterator.next();    // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 20
bSTIterator.hasNext(); // 返回 False
 

提示：

树中节点的数目在范围 [1, 105] 内
0 <= Node.val <= 106
最多调用 105 次 hasNext 和 next 操作
*/

// 法一
// Definition for a binary tree node.
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class BSTIterator {
private:
	stack<TreeNode*> st;
public:
	BSTIterator(TreeNode* root) {
		// 所有左子树压栈
		while (root != nullptr) {
			st.push(root);
			root = root->left;
		}
	}

	int next() {
		TreeNode* node = st.top();
		st.pop();
		// 有右子树，就处理右子树
		TreeNode* right = node->right;
		while (right != nullptr) {
			st.push(right);
			right = right->left;
		}
		return node->val;
	}

	bool hasNext() {
		return !st.empty();
	}
};

// 法二
class BSTIterator {
    TreeNode* dummy = nullptr;
    TreeNode* pre, *cur;

public:
    BSTIterator(TreeNode* root) {
        std::function<void(TreeNode*)> flatten = [&](TreeNode* r) {
            if(!r) return ;
            flatten(r->left);
            r->left = nullptr;
            pre->right = r;
            pre = r;
            flatten(r->right);
        };
        dummy = new TreeNode(-1);
        pre = dummy;
        cur = dummy;
        flatten(root);
    }
    
    int next() {
        cur = cur->right;
        return cur->val;
    }
    
    bool hasNext() {
        return cur->right;
    }
};


/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */
